package testit;

import java.util.ListIterator;
import java.util.NoSuchElementException;

/*
 * Helpfull Links:
 * http://algo.informatik.uni-freiburg.de/bibliothek/books/ad
 * -buch/k1/programs/
 * http://www.javabeginners.de/Sammlungen_und_Listen/Einfach_verkettete_Liste
 * .php Prof. E. Rahm - Uni Leipzig - Java
 * (dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap3.pdf)
 * http://www2.tcs.ifi.lmu.de/lehre/SS04/InfoII/loesungen/blatt9/
 */

public class BookingList {

	Link first;
	Link last;

	private void empty() {
		first = null;
		last = null;
	}

	public BookingList() {
		empty();
	}

	public ListIterator<Object> listIterator() {
		return new LinkedListIterator(this);
	}

	public Object getFirst() {
		if (first == null)
			throw new NoSuchElementException();
		else
			return first.data;
	}

	public Object getLast() {
		if (last == null)
			throw new NoSuchElementException();
		else
			return last.data;
	}

	public void addFirst(Object obj) {
		Link newLink = new Link();
		newLink.data = obj;
		newLink.next = first;
		newLink.prev = null;
		if (first == null) {
			first = newLink;
			last = newLink;
		} else {
			first.prev = newLink;
			first = newLink;
		}
	}

	public void addLast(Object obj) {
		Link newLink = new Link();
		newLink.data = obj;
		newLink.next = null;
		newLink.prev = last;
		if (first == null) {
			first = newLink;
			last = newLink;
		} else {
			last.next = newLink;
			last = newLink;
		}
	}

	public Object removeFirst() {
		if (first == null)
			throw new NoSuchElementException();
		Object obj = first.data;
		if (first == last)
			empty();
		else {
			first = first.next;
			first.prev = null;
		}
		return obj;
	}

	public Object removeLast() {
		if (last == null)
			throw new NoSuchElementException();
		Object obj = last.data;
		if (first == last)
			empty();
		else {
			last = last.prev;
			last.next = null;
		}
		return obj;
	}
	
}

class Link {

	public Object data;
	public Link next;
	public Link prev;
}

class LinkedListIterator implements ListIterator<Object>
 {
	private Link forward;
	private Link backward;
	private BookingList list;
	private Link lastReturned;
	private int cursor;

	public LinkedListIterator(BookingList l) {
		forward = l.first;
		backward = null;
		list = l;
		lastReturned = null;
		cursor = 0;
	}

	public void add(Object obj) {
		lastReturned = null;
		if (backward == null) {
			list.addFirst(obj);
			backward = list.first;
		} else if (!hasNext()) {
			list.addLast(obj);
			backward = backward.next;
		} else {
			Link newLink = new Link();
			newLink.data = obj;
			newLink.next = forward;
			newLink.prev = backward;
			backward.next = newLink;
			forward.prev = newLink;
			backward = newLink;
		}
		cursor++;
	}

	public boolean hasNext() {
		return forward != null;
	}

	public boolean hasPrevious() {
		return backward != null;
	}

	public Object next() {
		lastReturned = forward;
		backward = forward;
		forward = forward.next;
		cursor++;
		return backward.data;
	}

	public int nextIndex() {
		return cursor;
	}

	public Object previous() {
		lastReturned = backward;
		forward = backward;
		backward = backward.prev;
		cursor--;
		return forward.data;
	}

	public int previousIndex() {
		return cursor - 1;
	}

	public void remove() {
		if (lastReturned == null)
			throw new IllegalStateException();
		else {
			if (lastReturned.prev == null)
				list.removeFirst();
			else if (lastReturned.next == null)
				list.removeLast();
			else {
				lastReturned.prev.next = lastReturned.next;
				lastReturned.next.prev = lastReturned.prev;
			}
			if (lastReturned == backward)
				backward = lastReturned.prev;
			else
				forward = lastReturned.next;
			lastReturned = null;
		}
		cursor--;
	}

	public void set(Object obj) {
		lastReturned.data = obj;
	}
	
}


/*
 public class BookingList {

ListElement startElem = new ListElement(" ");

	public void LinkedList() {
	}

	public void addLast(	 o) {
		ListElement newElem = new ListElement(o);
		ListElement lastElem = getLastElem();
		lastElem.setNextElem(newElem);
	}

	public void insertAfter(Object prevItem, Object newItem) {
		ListElement newElem, nextElem, pointerElem;
		pointerElem = startElem.getNextElem();
		while (pointerElem != null && !pointerElem.getObj().equals(prevItem)) {
			pointerElem = pointerElem.getNextElem();
		}
		newElem = new ListElement(newItem);
		nextElem = pointerElem.getNextElem();
		pointerElem.setNextElem(newElem);
		newElem.setNextElem(nextElem);
	}

	public void delete(Object o) {
		ListElement le = startElem;
		while (le.getNextElem() != null && !le.getObj().equals(o)) {
			if (le.getNextElem().getObj().equals(o)) {
				if (le.getNextElem().getNextElem() != null)
					le.setNextElem(le.getNextElem().getNextElem());
				else {
					le.setNextElem(null);
					break;
				}
			}
			le = le.getNextElem();
		}
	}

	public boolean find(Object o) {
		ListElement le = startElem;
		while (le != null) {
			if (le.getObj().equals(o))
				return true;
			le = le.nextElem;
		}
		return false;
	}

	public ListElement getFirstElem() {
		return startElem;
	}

	public ListElement getLastElem() {
		ListElement le = startElem;
		while (le.getNextElem() != null) {
			le = le.getNextElem();
		}
		return le;
	}

	public void printList() {
		ListElement le = startElem;
		while (le != null) {
			System.out.println(le.getObj());
			le = le.getNextElem();
		}
	}

	public void clearList() {
		ListElement le = startElem;
		while (le.getNextElem() != null) {
			if (le.getNextElem().getNextElem() != null)
				le.setNextElem(le.getNextElem().getNextElem());
			else {
				le.setNextElem(null);
				break;
			}
		}
		le = le.getNextElem();
	}

}

class ListElement {

	Object obj;

	ListElement nextElem;

	public ListElement(Object obj) {
		this.obj = obj;
		nextElem = null;
	}

	public void setNextElem(ListElement nextElem) {
		this.nextElem = nextElem;
	}

	public ListElement getNextElem() {
		return nextElem;
	}

	public Object getObj() {
		return obj;
	}
}
 */